﻿#include <iostream>
#include <algorithm>
using namespace std;

int min(int a, int b, int c) {
	int min = a;								//假设x为最小数
	if (b < min) {
		min = b;
	}
	if (c < min) {
		min = c;
	}

	return min;
}

int ASM(char p[], int m, char t[], int n) {
	int i, j;
	int * *D = new int* [m + 1];
	for (i = 0; i <= m; i++) {
		D[i] = new int[n + 1];
	}

	for (i = 0; i <= m; i++) {					//初始化数组
		for (int j = 0; j <= n; j++) {
			D[i][j] = 0;
		}
	}

	for(j = 1; j <= n; j++) {					//根据递推式依次计算每一列
		for(i = 1; i <= m; i++) {
			if(p[i - 1] == t[j - 1]) {			//注意数组下标从0开始
				D[i][j] = ::min(D[i - 1][j - 1], D[i - 1][j] + 1, D[i][j - 1] + 1);
			} else {
				D[i][j] = ::min(D[i - 1][j - 1] + 1, D[i - 1][j] + 1, D[i][j - 1] + 1);
			}
		}
	}

	int a = D[m][n];
	for (i = 0; i <= m; i++) {
		delete[] D[i];
	}

	return a;
}

int main() {
	char p[] = {'h', 'a', 'p', 'p', 'y'};
	char t[] = {'h', 's', 'p', 'p', 'a', 'y'};
	cout << "最小差别数是：" << ASM(p, 5, t, 6) << endl;

	system("pause");
	return 0;
}